# 多重背包问题(Bounded Knapsack Problem)

"""题目
给定一个容量为W的背包和n个物品, 每个物品i有重量 wi 和价值 vi. 每个物品最多可以选择 ci 次. 求解如何在不超过背包容量的情况下选取物品使得总价值最大.
"""

def bounded_knapsack_base(W: int, items: list) -> int:
    """
    n: 物品数量
    W: 背包容量
    items: 每个物品的 (weight, value, count) 元组列表，其中 count 表示最多可选次数
    返回在不超过背包容量的情况下能取得的最大总价值
    """
    n = len(items)
    # dp[i][j] 表示前 i 个物品在容量为 j 时获得的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    # 遍历每个物品
    for i in range(1, n + 1):
        weight, value, count = items[i - 1]
        for j in range(W + 1):
            # 不选第 i 个物品时，继承上一行的状态
            dp[i][j] = dp[i - 1][j]
            # 枚举选取第 i 个物品的数量 k
            for k in range(1, count + 1):
                if j >= k * weight:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weight] + k * value)
                else:
                    break  # j 无法容纳 k 个物品，后续 k 也不可能满足条件
    return dp[n][W]


def bounded_knapsack_opt(W: int, items: list) -> int:
    """
    n: 物品数量
    W: 背包容量
    items: 每个物品的 (weight, value, count) 元组列表，其中 count 表示最多可选次数
    返回在不超过背包容量的情况下能取得的最大总价值
    """
    n = len(items)
    # dp[j] 表示容量为 j 时的最大价值
    dp = [0] * (W + 1)

    # 遍历每个物品
    for i in range(n):
        weight, value, count = items[i]
        # 逆序遍历背包容量，确保当前物品不会重复选取超过允许次数
        for j in range(W, -1, -1):
            # 枚举选取当前物品的数量 k
            for k in range(1, count + 1):
                if j >= k * weight:
                    dp[j] = max(dp[j], dp[j - k * weight] + k * value)
                else:
                    break
    return dp[W]

# 示例测试
if __name__ == '__main__':
    # 示例：3 个物品，背包容量 10
    # 物品格式: (重量, 价值, 最多可选次数)
    items = [
        (2, 3, 3),  # 物品1：重量 2，价值 3，最多选 3 次
        (3, 4, 2),  # 物品2：重量 3，价值 4，最多选 2 次
        (4, 5, 1)   # 物品3：重量 4，价值 5，最多选 1 次
    ]
    W = 10

    print(bounded_knapsack_base(W,items))
    print(bounded_knapsack_opt(W,items))